//https://leetcode.cn/problems/longest-consecutive-sequence/submissions/583033987/


class Solution {
public:
    // rt 记录每个元素的父节点（根指针），实现路径压缩
    // sz 记录以某个节点为根的集合大小
    unordered_map<int, int> rt, sz;

    // 查找函数（路径压缩优化）
    // 用于找到某元素所在集合的根节点
    int find(int v) {
        // 如果 v 是根节点，直接返回，否则递归查找父节点，并路径压缩
        return rt[v] == v ? v : rt[v] = find(rt[v]); 
    }

    // 合并两个集合（按大小合并优化）
    // 返回合并后的集合的大小
    int merge(int u, int v) {
        u = find(u); // 找到 u 的根节点
        v = find(v); // 找到 v 的根节点

        // 如果 u 和 v 不在同一个集合中，则合并
        if (u != v) {
            // 将 v 的根指向 u 的根，并累加集合大小
            sz[u] += sz[v];
            rt[v] = u;
        }
        // 返回合并后集合的大小
        return sz[u];
    }

    // 主函数：找到数组中最长连续序列的长度
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0; // 如果数组为空，返回 0

        int ans = 1; // 初始化答案为 1（最小连续序列长度为 1）

        // 初始化并查集
        for (int v : nums) {
            // 每个元素先独立成一个集合
            rt[v] = v; // 初始化自己指向自己
            sz[v] = 1; // 每个集合的初始大小为 1
        }

        // 遍历数组，尝试合并与 v-1 的集合
        for (int v : nums) {
            if (rt.find(v - 1) != rt.end()) {
                // 如果存在 v-1，将 v 和 v-1 合并，并更新最长连续序列长度
                ans = max(ans, merge(v, v - 1));
            }
        }

        return ans; // 返回最长连续序列的长度
    }
};
